import java.util.ArrayList;
import java.util.Arrays;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class CombinationSum {

	int n, target, sum, candidates[];
	ArrayList<ArrayList<Integer>> res;
	ArrayList<Integer> list;

	public void search(int idx, int depth) {
		if (sum == target) {
			res.add((ArrayList<Integer>) list.clone());
			return;
		}
		if (depth == n || sum + candidates[idx] > target)
			return;
		while (sum <= target) {
			search(idx + 1, depth + 1);
			sum += candidates[idx];
			list.add(candidates[idx]);
		}
		while (list.size() > 0 && list.get(list.size() - 1) == candidates[idx]) {
			list.remove(list.size() - 1);
			sum -= candidates[idx];
		}
	}

	public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates,
			int target) {
		res = new ArrayList<ArrayList<Integer>>();
		Arrays.sort(candidates);
		this.candidates = candidates;
		this.target = target;
		n = this.candidates.length;
		int j = 0;
		for (int i = 0; i < n;) {
			this.candidates[j++] = this.candidates[i++];
			while (i < n && this.candidates[i] == this.candidates[i - 1])
				i++;
		}
		n = j;
		list = new ArrayList<Integer>();
		sum = 0;
		search(0, 0);
		return res;
	}

	public static void main(String[] args) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(1);
		ArrayList<Integer> list2 = list;
		res.add(list2);
		list.add(2);
		System.out.println(res.get(0).size());
	}

}
